package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by 林剑 on 2016/10/8.
 */
public class sj {

    public int permute(int[] num) {
        ArrayList<Integer> cur = new ArrayList<Integer>();
        ArrayList<Integer> max = new ArrayList<Integer>();
        int res = 0;
        int item = 0;
        if(num.length==0||num==null)
            return 0;
        boolean[] visited = new boolean[num.length];

        permutation_helper(num,cur,max,visited);
        for (int i :max){
            if (i>res) res=i;
        }
        return res;
    }

    public void permutation_helper(int[] num, ArrayList<Integer> cur,ArrayList<Integer> max,boolean[] visited){
        if(cur.size()==num.length){

            boolean[] vis = new boolean[num.length];
            int item= 0;
            for (int i:cur){
                int left= 1,right =1;
                vis[i] =true;
                for (int j = i-1;j>=0;j--){
                    if (!vis[j]){
                        left = num[j];
                        break;
                    }
                }
                for (int k = i+1;k<num.length;k++){
                    if (!vis[k]) {
                        right = num[k];
                        break;
                    }
                }
                item+=num[i]*left*right;
            }

            max.add(item);
            return ;
        }

        for(int i = 0; i<num.length;i++){
            if(!visited[i]){
                visited[i]=true;
                cur.add(i);
                permutation_helper(num, cur, max, visited);
                cur.remove(cur.size()-1);
                visited[i]=false;
            }
        }
        return ;
    }
    public static void main(String[] args) {
        sj leetcode46 = new sj();
        int[] a = {3,1,5,8};
        System.out.println(leetcode46.permute(a));
    }
}
